#include "algorithmStrings.h"
#include <string>
using namespace std;

namespace algorithm
{
    /**
     * @brief 第3题
     * Get the Length of Longest Substring object
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     *
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * @param s
     * @return int
     */
    int GetLenOfLongestSubstring1(string s)
    {
        /**
         * 1.字符串长度为0时，则返回0；
         * 2.定义一个长度为256的数组,所有的ascii码；
         *
         */
        if (s.length() == 0)
            return 0;
        int bitSet[256] = {0};
        for (int i = 0; i < 256; i++)
        {
            bitSet[i] = -1;
        }

        int rst = 0, start = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int index = s.at(i);
            start = (start > bitSet[index] + 1) ? start : bitSet[index] + 1;
            rst = (rst > i - start + 1) ? rst : i - start + 1;
            bitSet[index] = i;
            // std::cout << rst << std::endl;
        }
        return rst;
    }

    int GetLenOfLongestSubstring(string s)
    {
        /**
         * 1.字符串长度为0时，则返回0；
         * 2.定义一个长度为256的数组,所有的ascii码；
         *
         */
        if (s.length() == 0)
            return 0;
        int bitSet[256] = {0};
        int rst = 0, start = 0, end = 0;
        while (start < s.length())
        {
            if (end < s.length() && bitSet[s.at(end)] == 0)
            {
                bitSet[s.at(end)] = 1;
                end++;
            }
            else
            {
                bitSet[s.at(start)] = 0;
                start++;
            }
            rst = (rst > end - start) ? rst : end - start;
        }
        return rst;
    }

    /**
     * @brief 每5题 最长回文子串
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     *
     * @param s
     * @return string
     */
    string LongestPalindrome(string s)
    {
        /**
         * @brief 算法思想
         * 1.判断字符串的长度是否小于2，当小于2时，即空或只有一个字符，则返回字符串本身；
         * 2.先确定一个中心点；
         * 3.从中心点向左右扩散，找到回文的两个边界
         * 4.记录下最长回文子串的边界；
         * 5.更新下中心点，此中心点为当前中心点的下个字符，即扩散后两边界的中心点+1，(left+right)/2+1
         * 6.重复2~5步直到中心点最后一个字符
         *
         */
        if (s.length() < 2)
            return s;
        int left = 0, right = 0, pl = 0, pr = 0;

        for (int i = 0; i < s.length(); i++)
        {
            //中心点
            left = i;
            right = i;
            // 判断left与left+1是相同字符的情况，此时应把right放入后一个字符位置,直到最后一个相同的字符
            while (right + 1 < s.length() && s.at(left) == s.at(right + 1))
                right++;

            // 从中心往两边扩散，直到不相等的最边界
            while (left - 1 > -1 && right + 1 < s.length() && s.at(left - 1) == s.at(right + 1))
            {
                left--;
                right++;
            }
            // 记录下回文子串最长的两个边界
            if (right - left > pr - pl)
            {
                pl = left;
                pr = right;
            }
        }
        return s.substr(pl, pr - pl + 1);
    }

    string LongestPalindrome1(string s)
    {
        if (s.length() < 2)
            return s;

        string nstr;
        for (int i = 0; i < s.length(); i++)
        {
            nstr.append("#");
            nstr.append(1, s.at(i));
        }
        nstr.append("#");

        int dp[nstr.length()] = {0};
        int maxRight = 0, center = 0, maxLen = 1, begin = 0;
        for (int i = 0; i < nstr.length(); i++)
        {
            if (i < maxRight)
                dp[i] = (maxRight - 1 < dp[2 * center - i]) ? maxRight - 1 : dp[2 * center - i];

            int left = i - (1 + dp[i]), right = i + (1 + dp[i]);
            while (left > -1 && right < nstr.length() && nstr.at(left) == nstr.at(right))
            {
                dp[i]++;
                left--;
                right++;
            }

            if (i + dp[i] > maxRight)
            {
                maxRight = i + dp[i];
                center = i;
            }
            if (dp[i] > maxLen)
            {
                maxLen = dp[i];
                begin = (i - maxLen) / 2;
            }
        }
        return s.substr(begin, maxLen);
    }
    /**
     * @brief 此算法是从网上抄的，速度最快
     * 与前面的方法区别：只是在比较字符串中字符时的方法不同，此方法用的数组下标的方法索引，
     * 前面用的是字符串的at方法，这个方法可能比较耗时。
     *
     * @param s
     * @return string
     */
    string LongestPalindrome2(string s)
    {
        if (s.length() < 2)
            return s;

        const int sLen = s.length();

        int max = 0, start = 0, i = 0;
        while (i < sLen)
        {
            int left = i, right = i;
            if (sLen - 1 < max / 2)
                break;
            while (right < sLen - 1 && s[right] == s[1 + right])
                right++;
            i = right + 1;
            while (right < sLen - 1 && left > 0 && s[1 + right] == s[left - 1])
            {
                left--;
                right++;
            }
            if (max < (right - left + 1))
            {
                start = left;
                max = right - left + 1;
            }
        }
        return s.substr(start, max);
    }
    /**
     * @brief 第6题. Z 字形变换
     * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
     * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
     * P   A   H   N
     * A P L S I I G
     * Y   I   R
     * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
     *
     * @param s 输入的字符串
     * @param numRows 待排列的行数
     * @return string 返回的字符串
     */
    string Convert(string s, int numRows)
    {
        if (numRows < 2)
            return s;

        const int num = numRows;
        string rst;

        /**
         * @brief 处理问题的步骤
         * 从问题的描述可知，第一行，从0开始每隔2*（numRows-1）取一个字符；
         * 最后一行，从numRows-1开始每隔2*（numRows-1）取一个字符；
         * 中间的第i行，在0~2*（numRows-1）范围内，取索引为i与2*（numRows-1）-i的字符。
         * 此前所有的操作前提都是索引不能越界。
         *
         */
        for (int i = 0; i < num; i++)
        {
            int idx = 0;
            while (idx < s.length())
            {
                if (i == 0)
                    rst.push_back(s[idx]);
                else if (i == num - 1 && idx + i < s.length())
                    rst.push_back(s[idx + i]);
                else
                {
                    if (idx + i < s.length())
                        rst.push_back(s[idx + i]);
                    if (idx + 2 * (num - 1) - i < s.length())
                        rst.push_back(s[idx + 2 * (num - 1) - i]);
                }
                idx += 2 * (num - 1);
            }
        }

        return rst;
    }
    /**
     * @brief 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
     * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     *     例如，121 是回文，而 123 不是。
     *
     * @param x
     * @return true
     * @return false
     */
    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
        long long inVal = x, rvsVal = 0;
        while (x)
        {
            if(rvsVal>(pow(2,31)-1-x%10)/10)return false;
            rvsVal = rvsVal * 10 + x % 10;
            x /= 10;
        }
        return rvsVal == inVal;
    }

//转成字符做法
    bool isPalindrome1(int x)
    {
        if (x < 0)
            return false;
        string s = to_string(x);
        std::cout << s.length() << std::endl;
        // 定位中心
        int left = (s.length() - 1) / 2;
        int right = s.length() / 2;
        std::cout << left << " -> " << right << std::endl;
        //如果只是两位数，则当前的left,right就是边界，但不一定相等，无法进入while循环
        if (s[left] != s[right])
            return false;

        // 从中心往两扩散
        while (right + 1 < s.length() && s[left - 1] == s[right + 1])
        {
            left--;
            right++;
        }
        return (left == 0 && right == s.length() - 1) ? true : false;
    }
}